import java.util.*;
public class Test {
    /*
    复习：
    题目 1 ： 寻找消失的那些数字
     */
    //以数组替代hash表，时间复杂度为O(1)
    //以数组元素重新作为数组下标，并将这个下标上的元素 + n
    //为了取到所有元素重新作为下标的原始值，都得将元素 % n，去除 +n 的影响
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list = new LinkedList<>() ;
        int n = nums.length;
        for(int i = 0; i < n; i++){
            int x = (nums[i] - 1) % n;
            nums[x] += n;
        }
        for(int i = 0; i < n; i++){
            if(nums[i] <= n){
                list.add(i + 1);
            }
        }
        return list;
    }

    /*
    题目 2 : 移动 0
     */
    //双指针
    //两种写法
    // 一是覆盖:
    public void moveZeroes1(int[] nums) {
        int left = 0;
        int right = 0;
        while(right < nums.length){
            if(nums[right] != 0){
                nums[left] = nums[right];
                left++;
                right++;
            }else{
                right++;
            }
        }
        while(left < nums.length){
            nums[left++] = 0;
        }
    }
    //二是交换:
    private void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public void moveZeroes2(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = 0;
        while(right < n){
            if(nums[right] != 0){
                swap(nums,left,right);
                left++;
                right++;
            }else{
                right++;
            }
        }
    }

    /*
    题目 3 ：和为 K 的连续子数组
     */
    //方法一 ：暴力枚举
    public static int subarraySum1(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        for(int i = 0; i < n; i++){
            //以下标 j 作为连续子数组的右边界
            int sum = 0;
            for(int j = i; j >= 0; j--){
                sum += nums[j];
                if(sum == k){
                    count++;
                }
            }
        }
        return count;
    }
    public static int subarraySum2(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        for(int i = 0; i < n; i++){
            //以下标 j 作为连续子数组的左边界
            int sum = 0;
            for(int j = i; j < n; j++){
                sum += nums[j];
                if(sum == k){
                    count++;
                }
            }
        }
        return count;
    }

    //方法二 ：前缀和 + 哈希表
    public static int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        int pre = 0;
        int count = 0;
        map.put(0,1);
        for(int i = 0; i < nums.length; i++){
            pre += nums[i];
            if(map.containsKey(pre - k)){
                count += map.get(pre - k);
            }
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

    /*
    题目4 ：递增的三元子序列
     */
    public boolean increasingTriplet(int[] nums) {
        if(nums.length < 3){
            return false;
        }
        int first = nums[0];
        int second = Integer.MAX_VALUE;
        //让 first 成为下标为 0 ~ i 之间的元素中最小的元素
        //让 second 成为第二小的元素
        //增加后面找到第三个递增元素的概率！！
        for(int i = 1; i < nums.length; i++){
            if(nums[i] > second){
                return true;
            }else if(nums[i] > first){
                second = nums[i];
            }else{
                first = nums[i];
            }
        }
        return false;
    }

    /*
    新题目：
    题目 1 ：汉明距离
     */
    //两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
    //思路：
    //异或运算，能得到 x 和 y 的二进制位数中，所有对应位上不同位的个数
    //这样原始问题就转换成 位计算问题
    //方法一：使用内置函数
    public int hammingDistance1(int x, int y) {
        return Integer.bitCount(x ^ y) ;
    }

    //方法二：按位与：同为 1 时，结果才为 1. 与 右移
    public int hammingDistance2(int x, int y) {
        int z = x ^ y;
        int count = 0;
        while(z > 0){
            count += z & 1;
            z >>= 1;
        }
        return count;
    }

    //方法3：
    //Brian Kernighan 算法：该算法可以被描述为这样一个结论：记 f(x) 表示 x 和 x−1 进行与运算所得的结果
    // （即 f(x) = x & (x−1)），那么 f(x) 恰为 x 删去其二进制表示中最右侧的 1 的结果。
    public int hammingDistance(int x, int y) {
        int z = x ^ y;
        int count = 0;
        while(z > 0){
            count ++;
            z &= (z - 1);
        }
        return count;
    }
////
    /*
    题目 2 : 最长公共前缀
     */
    //编写一个函数来查找字符串数组中的最长公共前缀。
    //如果不存在公共前缀，返回空字符串 ""。
    //横向扫描：公共前缀是所有单词的交集，以两个单词为单位，依次比较下去，更新公共前缀
    public String longestCommonPrefix1(String[] strs) {
        if(strs == null || strs.length == 0){
            return "";
        }
        String pre = strs[0];
        for(int i = 1; i < strs.length; i++){
            pre = commonPrefix(pre, strs[i]);
            if(pre.length() == 0){
                return "";
            }
        }
        return pre;
    }

    private String commonPrefix(String str1, String str2){
        int minlength = Math.min(str1.length(), str2.length());
        int index = 0;
        while(index < minlength && str1.charAt(index) == str2.charAt(index)){
            index++;
        }
        return str1.substring(0, index);
    }

    //纵向扫描：以第一个字符串为基准，依次取出字符，挨个与后面的字符串进行比较
    //这个是自己一开始的想法
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0 || strs == null){
            return "";
        }
        int count = strs.length;
        int length = strs[0].length();
        for(int i = 0; i < length; i++){
            char ch = strs[0].charAt(i);
            for(int j = 1; j < count; j++){
                if(i == strs[j].length() || strs[j].charAt(i) != ch)
                    return strs[0].substring(0, i);
            }
        }
        return strs[0];
    }
}
